"""
Problem 15: https://projecteuler.net/problem=15

Starting in the top left corner of a 2×2 grid, and only being able to move to
the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = Thonny Python3.7.3
@creat_time = 2022/5/7
'''

        
def solution1(N: int = 20) -> int:
    '''
    Start (0,0), END :(N, N), only two ways: (1, 0), or (0, 1)
    
        move    times
        -------------
        (1, 0)   N
        (0, 1)   N
    
    One route from (0,0) to (N, N) maps a sequence of (1, 0) * N, (0, 1) * N.
    The total of routes is combinatorial number C(2N, N) = (2N)! / (N! * N!).
    You can imagine a road with 2N stations; 
    if you chose N stations named (1, 0), the rest of stations must be (0, 1) 
    
    >>> solution1(1)
    2
    >>> solution1(2)
    6
    '''
    # from math import comb  # Python 3.8
    # return comb(2*N, N) 
    
    # from math import factorial
    # return factorial(2*N) // (factorial(N)**2)
    from functools import reduce
    return reduce(lambda x,y : x*y, range(N+1, 2*N + 1)) // (
           reduce(lambda x,y : x*y, range(1, N+1)))

def solution2(N: int = 20, M: int = 20) -> int:
    '''
    use recursion
    
    S(N, N) = S(N-1, N) + S(N, N-1)
    
    ************************************************
    !!! the recursion is too long
    
    if N == 0 or M == 0:
        return 1
    
    return solution2(N-1, M) + solution2(N, M-1)
    ************************************************
    
    >>> solution2(1,1)
    2
    >>> solution2(2,2)
    6
    >>> solution2(5,5)
    252
    
    The following method  s(n) = n^2 / 2   ~   O(n^2) additions
    '''
    
    record = [[0]*(N+1) for _ in range(M+1)]
    for i in range(N+1):
        for j in range(i, M+1):  # diagonal symmetric matrix, (i,j) = (j, i)
            if i == 0 or j == 0:
                record[i][j] = 1
                record[j][i] = 1
            else:
                record[i][j] = record[i-1][j] + record[i][j-1]
                record[j][i] = record[i][j]
    
    return record[N][M]



if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose = False)
    
    print(f'solution1() = {solution1()}')
    print(f'solution2() = {solution2()}')
    # 137846528820

    
    
    


    


